Merge sort is a popular divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts each half, and then merges the sorted halves back together. Here's a C++ implementation of merge sort with comments, along with sample Output:
#include <iostream>
#include
// Function to merge two sorted subarrays into one sorted array
void merge(std::vector& arr, int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
// Create temporary arrays to hold the left and right subarrays
std::vector leftArr(n1);
std::vector rightArr(n2);
// Copy data to temporary arrays leftArr[] and rightArr[]
for (int i = 0; i < n1; i++) {
leftArr[i] = arr[left + i];
}
for (int i = 0; i < n2; i++) {
rightArr[i] = arr[middle + 1 + i];
}
// Merge the two sorted arrays back into arr
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
// Copy the remaining elements of leftArr[], if any
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}
// Copy the remaining elements of rightArr[], if any
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
// Merge sort function
void mergeSort(std::vector& arr, int left, int right) {
if (left < right) {
// Find the middle point
int middle = left + (right - left) / 2;
// Recursively sort the first and second halves
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
// Merge the sorted halves
merge(arr, left, middle, right);
}
}
int main() {
std::vector arr = {64, 34, 25, 12, 22, 11, 90};
std::cout << "Original array: ";
for (int num : arr) {
std::cout << num << " ";
}
// Perform merge sort
mergeSort(arr, 0, arr.size() - 1);
std::cout << "\nSorted array: ";
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}
Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90
question
question2